package chapter02;

import java.util.Arrays;

public class UniquePathsWithObstacles63 {
    /**
     * 记忆化搜索
     * (0,0)->(m-1,n-1) 多少种走法
     * 递归出口
     *  1)x==m||y==n||obstacleGrid[x,y]==1
     *    return 0
     *  2)x==m-1&&y==n-1
     *    return 1
     *  3)没有出局 返回后续结果
     *    return process(x+1,y)+process(x,y+1)
     *  有些位置(x,y)会反复方便 增加一个dp[x][y]缓存该位置返回结果 节约时间
     *  动态规划
     *  根据递归改动态规划
     */
    //记忆化搜索
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int[][] dp=new int[obstacleGrid.length+1][obstacleGrid[0].length+1];
        for(int i=0;i<dp.length;i++){
            Arrays.fill(dp[i],-1);
        }
        return process(0,0,obstacleGrid,dp);
    }

    public int process(int x,int y,int[][] obstacleGrid,int[][] dp){
        if(dp[x][y]!=-1){
            return dp[x][y];
        }
        if(x==obstacleGrid.length||y==obstacleGrid[0].length||obstacleGrid[x][y]==1){
            dp[x][y]=0;
            return dp[x][y];
        }
        if(x==obstacleGrid.length-1&&y==obstacleGrid[0].length-1){
            dp[x][y]=1;
            return dp[x][y];
        }
        dp[x][y]=process(x+1,y,obstacleGrid,dp)+process(x,y+1,obstacleGrid,dp);
        return  dp[x][y];
    }

    //动态规划
    public int uniquePathsWithObstacles1(int[][] obstacleGrid){
        if(obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1]==1){
            return 0;
        }
        int[][] dp=new int[obstacleGrid.length+1][obstacleGrid[0].length+1];
        dp[dp.length-2][dp[0].length-2]=1;
        for(int j=dp[0].length-3;j>=0;j--){
            if(obstacleGrid[dp.length-2][j]==1){
                dp[dp.length-2][j]=0;
                continue;
            }
            dp[dp.length-2][j]=dp[dp.length-1][j]+dp[dp.length-2][j+1];
        }
        for(int i=dp.length-3;i>=0;i--){
            for(int j=dp[0].length-2;j>=0;j--){
                if(obstacleGrid[i][j]==1){
                    dp[i][j]=0;
                    continue;
                }
                dp[i][j]=dp[i+1][j]+dp[i][j+1];
            }
        }
        return dp[0][0];
    }
}
